{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Binary Subsequence Less Than or Equal to K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #memoization #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #记忆化搜索 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #小于等于 K 的最长二进制子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二进制字符串&nbsp;<code>s</code>&nbsp;和一个正整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <code>s</code>&nbsp;的 <strong>最长</strong>&nbsp;子序列，且该子序列对应的 <strong>二进制</strong>&nbsp;数字小于等于 <code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子序列可以有 <strong>前导 0</strong>&nbsp;。</li>\n",
    "\t<li>空字符串视为&nbsp;<code>0</code>&nbsp;。</li>\n",
    "\t<li><strong>子序列</strong>&nbsp;是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"1001010\", k = 5\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>s 中小于等于 5 的最长子序列是 \"00010\" ，对应的十进制数字是 2 。\n",
    "注意 \"00100\" 和 \"00101\" 也是可行的最长子序列，十进制分别对应 4 和 5 。\n",
    "最长子序列的长度为 5 ，所以返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"00101001\", k = 1\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>\"000001\" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。\n",
    "最长子序列的长度为 6 ，所以返回 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s[i]</code> 要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code> 。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-binary-subsequence-less-than-or-equal-to-k](https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-binary-subsequence-less-than-or-equal-to-k](https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"1001010\"\\n5', '\"00101001\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        dp = {}\n",
    "        answer = 1\n",
    "        for a in arr:\n",
    "            before_a = dp.get(a - difference, 0)\n",
    "            dp[a] = before_a + 1\n",
    "            answer = max(answer, dp[a])\n",
    "            \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        while arr:\n",
    "            x = arr.pop()\n",
    "            d[x] = d[x + difference] + 1\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        dp = {}\n",
    "        for num in arr:\n",
    "            dp[num] = 1\n",
    "            if num - difference in dp:\n",
    "                dp[num] = dp[num - difference] + 1\n",
    "        \n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        dp = dict()\n",
    "        for num in arr:\n",
    "            val = 0\n",
    "            val = dp.get(num - difference, 0) + 1\n",
    "            ans = max(ans, val)\n",
    "            dp[num] = val\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        place=dict()\n",
    "        dp=[0 for i in range(len(arr))]\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]-difference in place:\n",
    "                dp[i]=dp[place[arr[i]-difference]]+1\n",
    "                place[arr[i]]=i\n",
    "            else:\n",
    "                dp[i]=1\n",
    "                place[arr[i]]=i\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        Dic = {arr[0]:0}\n",
    "        F = [1 for a in range(len(arr))]\n",
    "        for a in range(1, len(arr)):\n",
    "            pre = arr[a]-difference \n",
    "            if pre in Dic.keys():\n",
    "                F[a] += F[Dic[pre]]\n",
    "            Dic[arr[a]] = a\n",
    "            #print([Dic, F])\n",
    "        \n",
    "        return max(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = dict()\n",
    "        ans = 0\n",
    "        for a in arr:\n",
    "            if a - difference in d:\n",
    "                d[a] = d[a-difference] + 1\n",
    "            else:\n",
    "                d[a] = 1\n",
    "            ans = max(ans, d[a])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = {}\n",
    "        for a in arr:\n",
    "            d[a] = d.get(a-difference,0)+1\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for num in arr:\n",
    "            d[num] = d[num - difference] + 1\n",
    "        return max(d.values())\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n=len(arr)\n",
    "        f0=[0]\n",
    "        f1=[1]\n",
    "        dt={}\n",
    "        dt[arr[0]]=0\n",
    "        for i in range(1,n):\n",
    "            f0.append(max(f0[i-1],f1[i-1]))\n",
    "            a=arr[i]\n",
    "            bf=a-difference\n",
    "            if bf in dt.keys():\n",
    "                f1.append(f1[dt[bf]]+1)\n",
    "            else:\n",
    "                f1.append(1)\n",
    "            dt[a]=i\n",
    "\n",
    "        return max(f0[n-1],f1[n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        # result = [1 for i in arr]\n",
    "        count = {}\n",
    "        for i in range(len(arr)):\n",
    "            if(arr[i] - difference in count):\n",
    "                count[arr[i]] = count[arr[i] - difference] + 1\n",
    "            else:\n",
    "                count[arr[i]] = 1\n",
    "        # print(count)\n",
    "        return max(count.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d = dict()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]-difference not in d.keys():\n",
    "                d[arr[i]] = 1\n",
    "                continue\n",
    "            d[arr[i]] = d[arr[i]-difference]+1\n",
    "        print(d)\n",
    "        return max(d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        dp = Counter()\n",
    "        for v in arr:\n",
    "            dp[v] = dp[v - difference] + 1\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        if not arr:return 0\n",
    "        n =len(arr)\n",
    "        # dp =[1]*n\n",
    "        # # 18 / 41 个通过的测试用例\n",
    "        # alist =[]\n",
    "        # for i in range(1,n):\n",
    "        #     for j in range(i):\n",
    "\n",
    "        #         if arr[i]-arr[j]==difference:\n",
    "        #             dp[i] =max(dp[i],dp[j]+1)\n",
    "        #         else:\n",
    "        #             dp[i] =max(dp[i],dp[j])\n",
    "        ans ={}\n",
    "        for i in arr:\n",
    "            if i-difference in ans:\n",
    "                ans[i] =ans[i-difference]+1\n",
    "            else:\n",
    "                ans[i] =1\n",
    "        return max(ans.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        #copy\n",
    "        subsequence = defaultdict(int)\n",
    "        for num in arr:\n",
    "            subsequence[num]= subsequence[num-difference] +1\n",
    "        return max(subsequence.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        d=defaultdict(int)\n",
    "        res=0\n",
    "        for a in arr:\n",
    "            d[a]=max(d[a],d[a-difference]+1)\n",
    "            res=max(res,d[a])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [1] * n\n",
    "        index = {arr[0]: 0}\n",
    "        last = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            if arr[i] - difference in index: last[i] = index[arr[i] - difference]\n",
    "            index[arr[i]] = i  \n",
    "        for i in range(1, n): \n",
    "            if last[i] != -1:\n",
    "                dp[i] += dp[last[i]]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        # dp[i]表示前i个的最长 - 1\n",
    "        n = len(arr)\n",
    "        dp = [0] * n\n",
    "        # 用哈希表存i前面的所有数的索引\n",
    "        idxhashtable = defaultdict(list)\n",
    "        idxhashtable[arr[0]].append(0)\n",
    "\n",
    "        # 找到前面的对应的数的idx\n",
    "        for i in range(1, n):\n",
    "            for idx in idxhashtable[arr[i] - difference]:\n",
    "                dp[i] = max(dp[i], dp[idx] + 1)\n",
    "            idxhashtable[arr[i]].append(i)\n",
    "        \n",
    "        return max(dp) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        s = set()\n",
    "        dp = collections.defaultdict(int)\n",
    "        for num in arr:\n",
    "            if num - difference in s:\n",
    "                dp[num] = max(dp[num], dp[num - difference] + 1)\n",
    "            s.add(num)\n",
    "        if dp:\n",
    "            return max(dp.values()) + 1\n",
    "        else:\n",
    "            return 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr)\n",
    "        f = [[0] * 2 for _ in range(1 + n)]\n",
    "        ##f[1][1] = 1\n",
    "        dic = {}\n",
    "        for i in range(1, 1 + n):\n",
    "            f[i][0] = max(f[i - 1][0], f[i - 1][1])\n",
    "            f[i][1] = max(f[i][1], dic.get(arr[i - 1] - difference, 0) + 1)\n",
    "            dic[arr[i - 1]] = f[i][1]\n",
    "\n",
    "        return max(f[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr)\n",
    "        mp = defaultdict(int)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][0] = 0 #不选择当前数字\n",
    "        dp[0][1] = 1 #不选择当前数字\n",
    "        mp[arr[0]]=1\n",
    "        for i in range (1,n):\n",
    "            dp[i][0] = max(dp[i-1][0],dp[i-1][1])\n",
    "            dp[i][1] = 1\n",
    "            pre = arr[i]-difference\n",
    "            if pre in mp:\n",
    "                dp[i][1] = mp[pre]+1\n",
    "            mp[arr[i]]=dp[i][1]\n",
    "        return max(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, arr: List[int], difference: int) -> int:\n",
    "        n = len(arr); dp = [1] * n; index = defaultdict(list)\n",
    "        for i, v in enumerate(arr):\n",
    "            index[v].append(i)\n",
    "        for i in range(1, n):\n",
    "            v = arr[i]\n",
    "            w = v - difference\n",
    "            for j in index[w]:\n",
    "                if j >= i: break\n",
    "                dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, a: List[int], dd: int) -> int:\n",
    "        n=len(a)\n",
    "        d=defaultdict(list)\n",
    "        ans=0\n",
    "        for i,c in enumerate(a):\n",
    "            d[c].append(i)\n",
    "        dp=[0]*n\n",
    "        ans=1\n",
    "        for i in range(1, n):\n",
    "            tt=a[i]-dd\n",
    "            if tt in d:\n",
    "                t0=bisect_left(d[tt], i)-1\n",
    "                t=d[tt][t0]\n",
    "                if t<i:\n",
    "                    dp[i]=max(2, dp[t]+1)\n",
    "                    ans=max(ans, dp[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = len(bin(k)[2:])\n",
    "        if m > n: return n\n",
    "        if int(s[n-m:], 2) <= k:\n",
    "            ans = m\n",
    "        else:\n",
    "            ans = m - 1\n",
    "        ans += s[:n-m].count('0')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        def num2bin(num:int)->str:\n",
    "            bin = \"\"\n",
    "            while(num!=0):\n",
    "                number = num//2\n",
    "                bin = str(num - number*2) + bin\n",
    "                num = number\n",
    "            return bin\n",
    "        def bin2num(bin:str)->int:\n",
    "            num = 0\n",
    "            k = 0\n",
    "            for i in range(-1,-len(bin)-1,-1):\n",
    "                num += int(bin[i]) * (2 ** k)  \n",
    "                k += 1\n",
    "            return num\n",
    "        bin = num2bin(k)\n",
    "        if len(bin) > len(s):\n",
    "            return len(s)\n",
    "        strbin = s[-len(bin):]\n",
    "        strnum = bin2num(strbin)\n",
    "        if(k >= strnum):\n",
    "            zeronum = 0\n",
    "            for i in range(0,len(s) - len(bin)):\n",
    "                if s[i] == '0':\n",
    "                    zeronum += 1\n",
    "            return zeronum + len(bin)\n",
    "        else:\n",
    "            zeronum = 0\n",
    "            for i in range(0,len(s) - len(bin)):\n",
    "                if s[i] == '0':\n",
    "                    zeronum += 1\n",
    "            return zeronum + len(bin) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        def num2bin(num:int)->str:\n",
    "            bin = \"\"\n",
    "            while(num!=0):\n",
    "                number = num//2\n",
    "                bin = str(num - number*2) + bin\n",
    "                num = number\n",
    "            return bin\n",
    "        def bin2num(bin:str)->int:\n",
    "            num = 0\n",
    "            k = 0\n",
    "            for i in range(-1,-len(bin)-1,-1):\n",
    "                num += int(bin[i]) * (2 ** k)  \n",
    "                k += 1\n",
    "            return num\n",
    "        bin = num2bin(k)\n",
    "        if len(bin) > len(s):\n",
    "            return len(s)\n",
    "        strbin = s[-len(bin):]\n",
    "        strnum = bin2num(strbin)\n",
    "        if(k >= strnum):\n",
    "            zeronum = 0\n",
    "            for i in range(0,len(s) - len(bin)):\n",
    "                if s[i] == '0':\n",
    "                    zeronum += 1\n",
    "            return zeronum + len(bin)\n",
    "        else:\n",
    "            zeronum = 0\n",
    "            for i in range(0,len(s) - len(bin)):\n",
    "                if s[i] == '0':\n",
    "                    zeronum += 1\n",
    "            return zeronum + len(bin) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        ans=s.count('0')\n",
    "        dp=[0]*n\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                dp[0]=1-int(s[0])\n",
    "            else:\n",
    "                dp[i]=dp[i-1]+1-int(s[i])\n",
    "        # print(dp)\n",
    "        k_s=bin(k)[2:]\n",
    "        for i in range(n):\n",
    "            if s[i]=='0':continue\n",
    "            index=0\n",
    "            minflag=len(s[i:])<len(k_s)\n",
    "            for j in range(i,n):\n",
    "                if index<len(k_s):\n",
    "                    if k_s[index]==s[j]:\n",
    "                        index+=1\n",
    "                    elif k_s[index]=='0' and s[j]=='1':\n",
    "                        if minflag:\n",
    "                            index+=1\n",
    "\n",
    "                    elif k_s[index]=='1' and s[j]=='0':\n",
    "                        index+=1\n",
    "                        minflag=1\n",
    "            \n",
    "            ans=max(ans,index+dp[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        if int(s[-m:], 2) <= k :\n",
    "            ans = m\n",
    "        else:\n",
    "            ans = m - 1\n",
    "        return ans + s[:-m].count('0')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        ans = s.count('0')\n",
    "        v = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '1':\n",
    "                v += 1 << (len(s) - i - 1)\n",
    "                if v <= k:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')\n",
    "\n",
    "# 这里的思想太离谱了\n",
    "# 针对二进制类的题目还是需要多练一下\n",
    "# 注意最高位一定是1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        # 基本思路：\n",
    "        # 首先，所有的零本身就是一个符合要求的最长子序列；\n",
    "        # 其次，从后往前添加1（贪心思想），直至子序列的值大于正整数k，此时即可得出答案！\n",
    "        str1 = ''\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                str1 = s[i] + str1\n",
    "            else:\n",
    "                if int(s[i] + str1, 2) <= k:\n",
    "                    str1 = s[i] + str1\n",
    "        return(len(str1))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        m = k.bit_length()\n",
    "        if n < m:\n",
    "            return n\n",
    "        ans = 0\n",
    "        if int(s[-m:], 2) <= k:\n",
    "            ans = m\n",
    "        else:\n",
    "            ans = m - 1\n",
    "        return ans + s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if int(s[i:], 2) <= k:\n",
    "                return n + len(s[i:])\n",
    "            if c == '0':\n",
    "                n += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = k.bit_length()\n",
    "        if m > n: return n\n",
    "        ans = m - 1\n",
    "        if int(s[n-m:], 2) <= k:\n",
    "            ans = m\n",
    "        ans += s.count('0', 0, n - m)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        if int(s, 2) <= k:\n",
    "            return len(s)\n",
    "        b = bin(k)[2:]\n",
    "        n = len(b)\n",
    "        right = s[-n:]\n",
    "        left = s[:-n]\n",
    "        ret = left.count('0') + n\n",
    "        if right > b:\n",
    "            ret -= 1\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        #贪心\n",
    "        n,m=len(s),k.bit_length()\n",
    "        if n<m: return n\n",
    "        ans=m if int(s[-m:],2)<=k else m-1\n",
    "        return ans+s[:-m].count(\"0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        cur = ''\n",
    "        for i in range(n-1, -1, -1):\n",
    "            prev = cur\n",
    "            cur = s[i] + prev\n",
    "            # 这一位不能加了\n",
    "            if int(cur, 2)> k: \n",
    "                break\n",
    "        # 统计s[:i]中0的个数\n",
    "        if int(cur, 2) <= k:\n",
    "            return len(cur)\n",
    "        else:\n",
    "            return s[:i].count('0') + len(cur) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        if int(s, 2) <= k: return len(s)\n",
    "        index = [x for x in range(len(s)) if s[x] == '1']\n",
    "        for i in range(len(index)):\n",
    "            s = s.replace(s[index[i]-i], '', 1)\n",
    "            if int(s, 2) <= k: return len(s)\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        m, n = len(s), k.bit_length()\n",
    "        if m < n: return m\n",
    "        res = -1\n",
    "        res = n if int(s[-n:],2) <= k else n-1\n",
    "        return res + s[:-n].count('0')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        cnt = 0\n",
    "        #prefix 0's at index\n",
    "        pre = []\n",
    "        for i, x in enumerate(s):\n",
    "            pre.append(cnt)\n",
    "            if x == '0':\n",
    "                cnt += 1\n",
    "        l = r = len(s) - 1\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        while l >= 0:\n",
    "            cur += int(s[l]) * 1 << (r - l)\n",
    "            # print(l, r, 'before', cur)\n",
    "            while cur > k:\n",
    "                cur -= int(s[r])\n",
    "                cur >>= 1\n",
    "                r -= 1\n",
    "            ans = max(ans, pre[l] + r - l + 1)\n",
    "            # print(l, r, 'after', cur)\n",
    "            l -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        #copy\n",
    "        n,m = len(s),k.bit_length()\n",
    "        if n <m:\n",
    "            return n\n",
    "        ans = m if int(s[-m:],2) <= k else m-1\n",
    "        return ans +s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        \n",
    "        # ans = 0\n",
    "        n = len(s)\n",
    "        # 倒序遍历,满足条件后+前面所有0 的个数\n",
    "        if int(s,2)<=k:\n",
    "            return n\n",
    "        # queue = collections.deque()\n",
    "        # for i in range(n):\n",
    "        #     if s[i] == '1':\n",
    "        #         queue.append(i)\n",
    "        i = 0\n",
    "        while int(s,2)>k:\n",
    "            if s[i] == '0':\n",
    "                i += 1\n",
    "            else:\n",
    "                s = s[:i]+s[i+1:]\n",
    "                \n",
    "                \n",
    "                \n",
    "        return len(s)\n",
    "                \n",
    "        \n",
    "        \n",
    "#         @cache\n",
    "#         def dfs(i,t):\n",
    "#             if t != '':\n",
    "#                 if int(t,2)>k:\n",
    "#                     return -n\n",
    "#             if i<0:\n",
    "#                 return 0\n",
    "#             return max(dfs(i-1,s[i]+t)+1,dfs(i-1,t))\n",
    "        \n",
    "#         ans = dfs(n-1,'')\n",
    "#         dfs.cache_clear()\n",
    "\n",
    "#         return ans\n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        def num2bin(num:int)->str:\n",
    "            bin = \"\"\n",
    "            while(num!=0):\n",
    "                number = num//2\n",
    "                bin = str(num - number*2) + bin\n",
    "                num = number\n",
    "            return bin\n",
    "        def bin2num(bin:str)->int:\n",
    "            num = 0\n",
    "            k = 0\n",
    "            for i in range(-1,-len(bin)-1,-1):\n",
    "                num += int(bin[i]) * (2 ** k)  \n",
    "                k += 1\n",
    "            return num\n",
    "        bin = num2bin(k)\n",
    "        if len(bin) > len(s):\n",
    "            return len(s)\n",
    "        strbin = s[-len(bin):]\n",
    "        strnum = bin2num(strbin)\n",
    "        print(strbin)\n",
    "        print(strnum)\n",
    "        if(k >= strnum):\n",
    "            zeronum = 0\n",
    "            for i in range(0,len(s) - len(bin)):\n",
    "                if s[i] == '0':\n",
    "                    zeronum += 1\n",
    "            print(zeronum)\n",
    "            return zeronum + len(bin)\n",
    "        else:\n",
    "            zeronum = 0\n",
    "            for i in range(0,len(s) - len(bin)):\n",
    "                if s[i] == '0':\n",
    "                    zeronum += 1\n",
    "            return zeronum + len(bin) - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        while int(s, 2) > k:\n",
    "            s = s.replace('1', '', 1)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\r\n",
    "        n, m = len(s), k.bit_length()\r\n",
    "        if n < m: return n\r\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\r\n",
    "        return ans + s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        cur_num = 0\n",
    "        for index in range(n - 1, -1, -1):\n",
    "            if s[index] == '1':\n",
    "                if cur_num + (1 << (n - index - 1)) > k:\n",
    "                    break\n",
    "                cur_num += (1 << (n - index - 1))\n",
    "                res += 1\n",
    "        return res + s.count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        ans = s.count('0')\n",
    "        val = 0\n",
    "        n = len(s)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '1':\n",
    "                tmp = 1 << (n - i - 1)\n",
    "                if val + tmp > k: break\n",
    "                ans += 1\n",
    "                val += tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        ans = s.count('0')\n",
    "        cnt = 0\n",
    "        t = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                t |= 1 << cnt\n",
    "                if t <= k:\n",
    "                    ans += 1\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n,m=len(s),k.bit_length()\n",
    "        if n<m:return n\n",
    "        ans=m if int(s[-m:],2) <= k else m-1\n",
    "        return ans+s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        k_bin=bin(k)[2:]\n",
    "        m=len(k_bin)\n",
    "        n=len(s)\n",
    "        if n<m:\n",
    "            return n\n",
    "        \n",
    "        sub=s[-m:]\n",
    "        if int(sub,2)<=k:\n",
    "            count=0\n",
    "            for i in range(n-m):\n",
    "                if s[i]=='0':\n",
    "                    count+=1\n",
    "            return count+m\n",
    "        else:\n",
    "            count=0\n",
    "            for i in range(n-m+1):\n",
    "                if s[i]=='0':\n",
    "                    count+=1\n",
    "            return count+m-1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        # 贪心\n",
    "        m = k.bit_length()\n",
    "        # 特殊情况\n",
    "        if n < m:\n",
    "            return n\n",
    "        ans = m - 1\n",
    "        # 判断 m长度的是否小于等于k\n",
    "        if int(s[-m:],2) <= k:\n",
    "            ans = m\n",
    "        return ans + s[:-m].count('0')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        print(n.bit_length())\n",
    "        if n < m: return n\n",
    "        if int(s[-m:], 2) <= k :\n",
    "            ans = m\n",
    "        else:\n",
    "            ans = m - 1\n",
    "        return ans + s[:-m].count('0')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n,m = len(s), k.bit_length()\n",
    "        if n<m:\n",
    "            return n\n",
    "        ans = m if int(s[-m:],2)<=k else m-1\n",
    "        return ans+s[:-m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n, m = len(s), k.bit_length()\n",
    "        if n < m: return n\n",
    "        ans = m if int(s[-m:], 2) <= k else m - 1\n",
    "        return ans + s[:-m].count('0')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = k.bit_length()\n",
    "        if n < m:\n",
    "            return n\n",
    "        ans = m - 1\n",
    "        if int(s[n - m:], 2) <= k:\n",
    "            ans = m\n",
    "        return ans + s[:n - m].count('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        # 贪心\n",
    "        n = len(s)\n",
    "        m = k.bit_length()\n",
    "        # 特判\n",
    "        if n < m:\n",
    "            return n\n",
    "        ans = m - 1\n",
    "        if int(s[-m:],2) <= k:\n",
    "            ans = m\n",
    "        ans += s[:-m].count('0')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequence(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        zeros = 0\n",
    "        if k == 1:\n",
    "            for c in s:\n",
    "                if c == '1':\n",
    "                    res = max(res, zeros + 1)\n",
    "                else:\n",
    "                    zeros += 1\n",
    "            res = max(res, zeros)\n",
    "        else:\n",
    "            n = len(s)\n",
    "            b = bin(k)[2:]\n",
    "            m = len(b)\n",
    "            m_right = m - 1\n",
    "            p = -1\n",
    "            p_best = -1\n",
    "            for i in range(n):\n",
    "                if s[i] == '1':\n",
    "                    n_right = n - i\n",
    "                    if n_right > m_right:\n",
    "                        p = i\n",
    "                        p_best = zeros + m_right\n",
    "                        res = max(res, p_best)\n",
    "                    else:\n",
    "                        res = max(res, zeros + n_right)\n",
    "                else:\n",
    "                    zeros += 1\n",
    "            res = max(res, zeros)\n",
    "            if p_best == res and self.test(s[p:], b):\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "    def test(self, s1, s2) -> bool:\n",
    "        n1, n2, i1, i2 = len(s1), len(s2), 0, 0\n",
    "        while i1 < n1 and i2 < n2:\n",
    "            if s1[i1] > s2[i2]:\n",
    "                i1 += 1\n",
    "            elif s1[i1] < s2[i2]:\n",
    "                return n1 - i1 >= n2 - i2\n",
    "            else:\n",
    "                i1, i2 = i1 + 1, i2 + 1\n",
    "        return i2 == n2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
